package DAC;

/**
 * 利用分治算法：解决汉诺塔问题
 */
public class DACHanoiTower {
    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }

    /**
     * @param num 要移动的个数
     * @param a 起始位置
     * @param b 中转位置
     * @param c 目标位置
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        // 如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘从" + a + "->" + c);
        } else {
            // 如果我们有n >= 2情况 我们总是可以看做是两个盘 1 最下面的盘 2 上面所有的盘
            // 1 先把上面的盘 a - > b  移动过程暂存到c
            hanoiTower(num- 1, a, c, b);
            // 2 最下面的盘 a - > c
            System.out.println("第"+num+"个盘从" + a + "->" + c);
            // 3 上面的盘 b - > c   移动过程暂存到a
            hanoiTower(num- 1, b, a, c);
        }

    }
}
